There are many real-time processors that associate incoming data with outgoing data. One example is a network processor. A network processor receives incoming packets, each of which may have a relationship with one or more packets that previously passed through the network processor. The network processor attempts to match a current packet with information from packets that have previously passed through the network processor. As an example, in network address translation (NAT), a network processor requires a way to store information (commonly called “state”) contained in one packet for matching against subsequent packets. State storage, retrieval, update, and deletion, each of which is based on a “key” associated with a packet, must generally operate within tight time constraints.
Content addressable memory (CAM) is a memory type that allows key-oriented information to be stored and quickly retrieved. CAM performs parallel searches on entries in the CAM. In other words, a network processor could order a search for “Key a” in a CAM, every entry in the CAM would compare its contents with “Key a,” and every entry that contained “Key a” would be quickly found and marked. Typically, in NAT, there is either one entry or no entries that contain the key.
CAM, however, is very expensive. Not only is a comparator used for every entry, but each entry generally contains a substantial amount of information. For instance, each entry could contain a 64-bit key and associated data, or a reference to a location in cheaper memory, such as dynamic random access memory (DRAM) or static random access memory (SRAM), where the associated data is stored. The reference can contain a relatively high number of bits, meaning that each CAM entry can be relatively large, such as 128 bits or more. The combination of a large memory with individual comparators for each entry causes CAM to be expensive.
There are also data structures implemented in cheaper memory that are suitable for accessing key-oriented information. One such data structure is a hash table. A hash function is used to access a hash table. Broadly, a hash function accepts an input key and selects an entry in the hash table based on the key. If no entry is found, the key and associated data are added to the hash table. If an entry becomes untimely or is no longer used, the entry is deleted.
These operations on hash tables mean that hash tables become harder to manage with the passage of time, particularly for a processor that needs to retrieve keys and associated data within tight time constraints. As hash tables have more entries and deletions, it generally takes longer, on average, to retrieve a key and its associated data. As described in more detail below, deletions for many types of hash tables do not decrease the time it takes to retrieve a key.
Moreover, certain types of hash tables are not particularly suitable for processors that support multithreading. During multithreading, multiple threads can contest for the same memory. Certain types of hash tables require a portion of memory that needs to be locked by a thread during operations such as adding a key and its associated data to the hash table. When this memory portion is locked, no other thread has access to the memory portion and, consequently, cannot add a key or its associated data to the hash table. This leads to unacceptable delays in many real-time processors.
A need therefore exists for techniques that speed accesses to hash tables, allow relatively cheap memory to be used for hash tables, and allow multiple threads to access a hash table with relatively low delay.